package com.kiven.quicksort;

/**
 *  用非递归实现快速排序时需要用到堆栈，这个堆栈主要存放的是子数组的左右下标值
 * @author liqingwen
 *
 */
public class LinkedStack {
	private Node first;
	
	public LinkedStack() {
		first = null;
	}
	
	//将一个节点压入堆栈
	public void push(int left,int right) {
		Node newNode = new Node(left,right);
		if(first == null) {
			first = newNode;
			//return语句的作用是终止该方法的调用，如果条件成立时，return下面的语句就不执行
			return;
		}
		
		newNode.setNext(first);
		first = newNode;
	}
	
	//弹出堆栈的第一个节点
	public Node pop() {
		Node temp = first;
		first = temp.getNext();
		return temp;
	}
	
	//获得堆栈的第一个节点
	public Node peek() {
		return first;
	}
	
	//判对该堆栈是否为空
	public boolean isEmpty() {
		return first == null;
	}
}


/**
 * 定义堆栈内的一个节点类
 * 该节点类的作用的保存未排序的子数组，并且将该字数组的首尾下标值保存在该节点中
 * @author liqingwen
 *
 */
class Node {
	private int right;  //保存未元素的下标值
	private int left;	//保存头元素的下标值
	private Node next;	//保存下一个节点
	
	public Node(int left,int right) {
		this.left = left;
		this.right = right;
		this.next = null;
	}
	
	public int getLeft() {
		return left;
	}
	
	public int getRight() {
		return right;
	}
	
	public void setNext(Node node) {
		this.next = node;
	}
	
	public Node getNext() {
		return this.next;
	}
}